Navigation systems use navigation map databases to provide users with route calculation, guidance, point-of-interest search and other navigation functions. Navigation map databases typical include data representing road networks and attributes such as in the format described by the KIWI format published by the KIWI-W Consortium, version 1.22, May 2000, incorporated herein by reference. Navigation system performance depends on valid data and, therefore, it is important to update or renew the navigation map database when road networks or their elements change significantly, for example, due to road construction. Renewal of a navigation map database can be accomplished by: (i) replacing the database, (ii) modifying the database or (iii) patching the database. The large size of a wide-area navigation map database renders modifying or patching parts of the database a preferred method for renewal by wireless communications. Some navigation map databases are stored on read-only medium such as CD-ROMs or DVD-ROMs. This adds an additional constraint that the original map database may not be modified and presents unique challenges for patching. While correlating update information with the original database is a common challenge regardless of the type of medium, the build up of patched data after multiple renewals may complicate renewal further. Furthermore, since a patch can be maintained separately from original data, a method of efficient renewal and seamless and stable access by applications is also required.
Different versions of navigation map databases and different sources of navigation map database data contribute to a large variation in detailed data contents among navigation system databases and render identification of the road network parts that have changed problematic due to their version dependence. Additionally, some users may miss or skip updates or partially update their database with regions of interest and therefore further contribute to the number of different database versions in use. For example between databases, the geographic locations and attributes of road structures may be significantly different, the identification assigned to a road structure may be different or even somewhat random, and the road network structures used to represent a road network section may be different. It is not uncommon for roads to have no name, for example. However, keeping track of all versions and sending updates tailored to specific navigation systems lacks robustness and is inflexible and inefficient, both in storage and use of communication bandwidth. Therefore, a method is required to identify a road network element to be updated that is flexible enough to function with multiple database versions and to function on database versions that have previously been modified, in whole or in part.
The present invention focuses on solving the above problems by a renewal operation that identifies modified road network elements independent of database version-specific information and does not necessarily require modification of an original database.